|
The Teiresias algorithm is a combinatorial algorithm for the discovery of rigid patterns (motifs) in biological sequences. It is named after the Greek prophet Teiresias and was created in 1997 by Isidore Rigoutsos and Aris Floratos.〔(Rigoutsos, I, Floratos, A (1998) Combinatorial pattern discovery in biological sequences: The TEIRESIAS algorithm. Bioinformatics 14: 55-67 )〕 The problem of finding sequence similarities in the primary structure of related proteins or genes is one of the problems arising in the analysis of biological sequences. It can be shown that pattern discovery in its general form is NP-hard.〔Maier, D., "The Complexity of Some Problems on Subsequences and Supersequences", Journal of the ACM, 322-336, 1978〕 The Teiresias algorithm, is based on the observation that if a pattern spans many positions and appears exactly k times in the input then all fragments (sub patterns) of the pattern have to appear at least k times in the input. The algorithm is able to produce all patterns that have a user-defined number of copies in the given input, and manages to be very efficient by avoiding the enumeration of the entire space. Finally, the algorithm reports motifs that are maximal in both length and composition. A new implementation of the Teiresias algorithm was recently made available by the . Teiresias is also accessible through an interactive web-based user interface by the same center. See external links for both. ==Pattern description== The Teiresias algorithm uses regular expressions to define the patterns. This allows the patterns reported to consist not only from the characters that appear in each position (literals) but from a specific group of characters (bracketed literals) or even from any character (wild card). The patterns created by the algorithm are The algorithm reports only maximal patterns. Given a set of sequences S, a pattern P that appears k times in S is called maximal if and only if there exists no pattern P' which is more specific than P and also appears exactly k times in S. If there exists such a pattern P' then we say that P cannot be maximal and P is considered to be subsumed by P'. A pattern P' is said to be more specific than a pattern P if and only if P' can be obtained from P by a) dereferencing a wild card or b) instantiating a bracketed literal to a literal, or c) by appending a string of literals, bracketed literals or/and wild cards to the right of P,or d) by prepending a string of literals, bracketed literals or/and wild cards to the left of P.〔Floratos A., and Rigoutsos, I., "On the time complexity of the Teiresias algorithm", IBM technical report RC 21161 (94582), IBM TJ Watson Research Center, 1998〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Teiresias algorithm」の詳細全文を読む スポンサード リンク
|